/*
 * @Author: gggg 1263457581@qq.com
 * @Date: 2025-06-03 09:09:57
 * @LastEditors: gggg 1263457581@qq.com
 * @LastEditTime: 2025-06-03 15:19:22
 * @FilePath: /algorithm-and-data-struct/datastruct/list/lru.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
#include <iostream>
#include <map>
#include <deque>

class Node{
public:
    int key;
    int value;
    Node*pre = nullptr;
    Node*next = nullptr;
    Node(int key, int value){
        this->key = key;
        this->value = value;
    }
};

template<typename K, typename V>
class LruCache{
public:
    LruCache(){
        this->capacity = 10;
    }
    LruCache(int capacity){
        this->capacity = capacity;
    }
    V get(K key){
        if(map.find(key) == map.end()){
            return -1;
        } else {
            auto it = map[key];
            lrulist.erase(it);
            lrulist.push_front(make_pair(key, map[key]));
            map[key] = lrulist.begin();
            return map[key]->second;
        }
    }

private:
    int capacity;
    deque<pair<K,V> > lrulist;
    unorder_map<K, list<pair<K,V>::iterator > map; //哈希表记录key值
    
}